/**
 * @program: leetcode543
 * @author: JCM
 * @create: 2022-11-20 10:03
 * @description: 二叉树的直径
 **/
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
// 求二叉树的深度
class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int lenleft = maxDepth(root.left)+1;
        int lenright = maxDepth(root.right)+1;
        return Math.max(lenleft,lenright);
    }
}
public class leetCode543 {
    public int ans = 1;
    public int diameterOfBinaryTree(TreeNode root) {
        depth(root);
        return ans - 1;

    }
    public int depth(TreeNode root) {
        if(root == null) {
            return 0;//遇到空节点，返回0
        }
        int lenleft = depth(root.left);//左子树的深度
        int lenright = depth(root.right);//右子树的深度
        ans = Math.max(ans,lenleft+lenright+1);//实时更新最大深度
        return Math.max(lenleft,lenright)+1;
    }

}

